package com.hainiu.cat.web.codeStudy;

import org.springframework.util.CollectionUtils;

import java.util.List;
import java.util.stream.Collectors;

/**
 * create by biji.zhao on 2021/5/23
 */
public class jvm {

    public static void main(String[] args) {
        /**
         * 0  0
         * 1  1
         * 2  [1, 1] 2
         * 3  [1 1 1] [1, 2] [2, 1]  3
         * 4  [1,1,1,1] [1,2,1],[1,1,2],[2,1,1] [2,2]
         * 5 [1,1,1,1,1],[1,1,1,2],[]
         */
        System.out.println(jumpCount(4));


    }


    public static int jumpCount(int n){
        if (n==0){
            return 0;
        }
        if (n==1){
            return 1;
        }
        return jumpCount(n-1)+jumpCount(n-2);
    }

    private static boolean contains(List<List<Integer>> maxTre, List<List<Integer>> minTree) {
        if (CollectionUtils.isEmpty(maxTre) || CollectionUtils.isEmpty(minTree)) {
            return false;
        }
        int minSize = minTree.size();
        int maxSize = maxTre.size();
        if (maxSize < minSize) {
            return false;
        }
        List<List<Integer>> allEqualFirst = maxTre.stream()
                .filter(e -> !listContains(e, minTree.get(0))).collect(Collectors.toList());
        if (CollectionUtils.isEmpty(allEqualFirst)) {
            return false;
        }
        for (int i = 0; i < maxTre.size(); i++) {
            for (List<Integer> equalOne : allEqualFirst) {
                if (listContains(maxTre.get(i), equalOne)) {
                    boolean compare = compare(maxTre.subList(i, minTree.size()), minTree);
                    if (!compare) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private static boolean compare(List<List<Integer>> maxTre, List<List<Integer>> minTree) {
        for (int i = 0; i < maxTre.size(); i++) {
            for (int j = 0; j < minTree.size(); j++) {
                if (!listContains(maxTre.get(i), minTree.get(i))) {
                    return false;
                }
            }
        }

        return true;
    }

    private static boolean listContains(List<Integer> one, List<Integer> two) {
        if (CollectionUtils.isEmpty(one) || CollectionUtils.isEmpty(two)) {
            return false;
        }
        if (one.size() < two.size()) {
            return false;
        }
        List<Integer> subList = one.subList(0, two.size());

        for (int i = 0; i < two.size(); i++) {
            if (!two.get(i).equals(subList.get(i))) {
                return true;
            }
        }
       return false;
    }

}
